package org.nowcoder.leetcode.DP;

/**
 * Title  : 64. Minimum Path Sum
 * Source : https://leetcode.cn/problems/minimum-path-sum/description/
 * Author : XrazYang
 * Date   : 2023-12-14
 */
public class LeetCode_64 {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        //1. 定义状态：min[m][n] : (0,0) -> (m,n)的最短路径
        int[][] path = new int[m][n];

        //2. 初始状态
        path[0][0] = grid[0][0];
        for (int i = 1; i < n; i++) {
            path[0][i] = path[0][i - 1] + grid[0][i];
        }

        for (int i = 1; i < m; i++) {
            path[i][0] = path[i - 1][0] + grid[i][0];
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                //3. 状态转移方程
                path[i][j] = Math.min(path[i - 1][j], path[i][j - 1]) + grid[i][j];
            }
        }
        return path[m - 1][n - 1];
    }
}
